home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 2 / Amiga Tools 2.iso / tools / vim / src / undo.c < prev    next >
C/C++ Source or Header  |  1995-03-09  |  25KB  |  964 lines
  1. /* vi:ts=4:sw=4
  2.  *
  3.  * VIM - Vi IMproved        by Bram Moolenaar
  4.  *
  5.  * Read the file "credits.txt" for a list of people who contributed.
  6.  * Read the file "uganda.txt" for copying and usage conditions.
  7.  */
  8.  
  9. /*
  10.  * undo.c: multi level undo facility
  11.  *
  12.  * The saved lines are stored in a list of lists (one for each buffer):
  13.  *
  14.  * b_u_oldhead------------------------------------------------+
  15.  *                                                            |
  16.  *                                                            V
  17.  *                +--------------+    +--------------+    +--------------+
  18.  * b_u_newhead--->| u_header     |    | u_header     |    | u_header     |
  19.  *                |     uh_next------>|     uh_next------>|     uh_next---->NULL
  20.  *         NULL<--------uh_prev  |<---------uh_prev  |<---------uh_prev  |
  21.  *                |     uh_entry |    |     uh_entry |    |     uh_entry |
  22.  *                +--------|-----+    +--------|-----+    +--------|-----+
  23.  *                         |                   |                   |
  24.  *                         V                   V                   V
  25.  *                +--------------+    +--------------+    +--------------+
  26.  *                | u_entry      |    | u_entry      |    | u_entry      |
  27.  *                |     ue_next  |    |     ue_next  |    |     ue_next  |
  28.  *                +--------|-----+    +--------|-----+    +--------|-----+
  29.  *                         |                   |                   |
  30.  *                         V                   V                   V
  31.  *                +--------------+            NULL                NULL
  32.  *                | u_entry      |
  33.  *                |     ue_next  |
  34.  *                +--------|-----+
  35.  *                         |
  36.  *                         V
  37.  *                        etc.
  38.  *
  39.  * Each u_entry list contains the information for one undo or redo.
  40.  * curbuf->b_u_curhead points to the header of the last undo (the next redo), or is
  41.  * NULL if nothing has been undone.
  42.  *
  43.  * All data is allocated with u_alloc_line(), thus it will be freed as soon as
  44.  * we switch files!
  45.  */
  46.  
  47. #include "vim.h"
  48. #include "globals.h"
  49. #include "proto.h"
  50. #include "param.h"
  51.  
  52. static void u_getbot __ARGS((void));
  53. static int u_savecommon __ARGS((linenr_t, linenr_t, linenr_t));
  54. static void u_undoredo __ARGS((void));
  55. static void u_undo_end __ARGS((void));
  56. static void u_freelist __ARGS((struct u_header *));
  57. static void u_freeentry __ARGS((struct u_entry *, long));
  58.  
  59. static char_u *u_blockalloc __ARGS((long_u));
  60. static void u_free_line __ARGS((char_u *));
  61. static char_u *u_alloc_line __ARGS((unsigned));
  62. static char_u *u_save_line __ARGS((linenr_t));
  63.  
  64. static long        u_newcount, u_oldcount;
  65.  
  66. /*
  67.  * save the current line for both the "u" and "U" command
  68.  */
  69.     int
  70. u_save_cursor()
  71. {
  72.     return (u_save((linenr_t)(curwin->w_cursor.lnum - 1), (linenr_t)(curwin->w_cursor.lnum + 1)));
  73. }
  74.  
  75. /*
  76.  * Save the lines between "top" and "bot" for both the "u" and "U" command.
  77.  * "top" may be 0 and bot may be curbuf->b_ml.ml_line_count + 1.
  78.  * Returns FALSE when lines could not be saved.
  79.  */
  80.     int
  81. u_save(top, bot)
  82.     linenr_t top, bot;
  83. {
  84.     if (top > curbuf->b_ml.ml_line_count || top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
  85.         return FALSE;    /* rely on caller to do error messages */
  86.  
  87.     if (top + 2 == bot)
  88.         u_saveline((linenr_t)(top + 1));
  89.  
  90.     return (u_savecommon(top, bot, (linenr_t)0));
  91. }
  92.  
  93. /*
  94.  * save the line "lnum" (used by :s command)
  95.  * The line is replaced, so the new bottom line is lnum + 1.
  96.  */
  97.     int
  98. u_savesub(lnum)
  99.     linenr_t    lnum;
  100. {
  101.     return (u_savecommon(lnum - 1, lnum + 1, lnum + 1));
  102. }
  103.  
  104. /*
  105.  * a new line is inserted before line "lnum" (used by :s command)
  106.  * The line is inserted, so the new bottom line is lnum + 1.
  107.  */
  108.      int
  109. u_inssub(lnum)
  110.     linenr_t    lnum;
  111. {
  112.     return (u_savecommon(lnum - 1, lnum, lnum + 1));
  113. }
  114.  
  115. /*
  116.  * save the lines "lnum" - "lnum" + nlines (used by delete command)
  117.  * The lines are deleted, so the new bottom line is lnum.
  118.  */
  119.     int
  120. u_savedel(lnum, nlines)
  121.     linenr_t    lnum;
  122.     long        nlines;
  123. {
  124.     return (u_savecommon(lnum - 1, lnum + nlines, lnum));
  125. }
  126.  
  127.     static int 
  128. u_savecommon(top, bot, newbot)
  129.     linenr_t top, bot;
  130.     linenr_t newbot;
  131. {
  132.     linenr_t        lnum;
  133.     long            i;
  134.     struct u_header *uhp;
  135.     struct u_entry    *uep;
  136.     long            size;
  137.  
  138.     /*
  139.      * if curbuf->b_u_synced == TRUE make a new header
  140.      */
  141.     if (curbuf->b_u_synced)
  142.     {
  143.         /*
  144.          * if we undid more than we redid, free the entry lists before and
  145.          * including curbuf->b_u_curhead
  146.          */
  147.         while (curbuf->b_u_curhead != NULL)
  148.             u_freelist(curbuf->b_u_newhead);
  149.  
  150.         /*
  151.          * free headers to keep the size right
  152.          */
  153.         while (curbuf->b_u_numhead > p_ul && curbuf->b_u_oldhead != NULL)
  154.             u_freelist(curbuf->b_u_oldhead);
  155.  
  156.         if (p_ul < 0)            /* no undo at all */
  157.             return TRUE;
  158.  
  159.         /*
  160.          * make a new header entry
  161.          */
  162.         uhp = (struct u_header *)u_alloc_line((unsigned)sizeof(struct u_header));
  163.         if (uhp == NULL)
  164.             goto nomem;
  165.         uhp->uh_prev = NULL;
  166.         uhp->uh_next = curbuf->b_u_newhead;
  167.         if (curbuf->b_u_newhead != NULL)
  168.             curbuf->b_u_newhead->uh_prev = uhp;
  169.         uhp->uh_entry = NULL;
  170.         uhp->uh_cursor = curwin->w_cursor;        /* save cursor position for undo */
  171.         uhp->uh_changed = curbuf->b_changed;    /* save changed flag for undo */
  172.                                                 /* save named marks for undo */
  173.         memmove((char *)uhp->uh_namedm, (char *)curbuf->b_namedm, sizeof(FPOS) * NMARKS); 
  174.         curbuf->b_u_newhead = uhp;
  175.         if (curbuf->b_u_oldhead == NULL)
  176.             curbuf->b_u_oldhead = uhp;
  177.         ++curbuf->b_u_numhead;
  178.     }
  179.     else    /* find line number for ue_bot for previous u_save() */
  180.         u_getbot();
  181.  
  182.     size = bot - top - 1;
  183. #ifndef UNIX
  184.         /*
  185.          * With Amiga and MSDOS we can't handle big undo's, because then
  186.          * u_alloc_line would have to allocate a block larger than 32K
  187.          */
  188.     if (size >= 8000)
  189.         goto nomem;
  190. #endif
  191.  
  192.     /*
  193.      * add lines in front of entry list
  194.      */
  195.     uep = (struct u_entry *)u_alloc_line((unsigned)sizeof(struct u_entry));
  196.     if (uep == NULL)
  197.         goto nomem;
  198.  
  199.     uep->ue_size = size;
  200.     uep->ue_top = top;
  201.     uep->ue_lcount = 0;
  202.     if (newbot)
  203.         uep->ue_bot = newbot;
  204.         /*
  205.          * use 0 for ue_bot if bot is below last line or if the buffer is empty, in
  206.          * which case the last line may be replaced (e.g. with 'O' command).
  207.          */
  208.     else if (bot > curbuf->b_ml.ml_line_count || bufempty())
  209.         uep->ue_bot = 0;
  210.     else
  211.         uep->ue_lcount = curbuf->b_ml.ml_line_count;    /* we have to compute ue_bot later */
  212.  
  213.     if (size)
  214.     {
  215.         if ((uep->ue_array = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * size))) == NULL)
  216.         {
  217.             u_freeentry(uep, 0L);
  218.             goto nomem;
  219.         }
  220.         for (i = 0, lnum = top + 1; i < size; ++i)
  221.         {
  222.             if ((uep->ue_array[i] = u_save_line(lnum++)) == NULL)
  223.             {
  224.                 u_freeentry(uep, i);
  225.                 goto nomem;
  226.             }
  227.         }
  228.     }
  229.     uep->ue_next = curbuf->b_u_newhead->uh_entry;
  230.     curbuf->b_u_newhead->uh_entry = uep;
  231.     curbuf->b_u_synced = FALSE;
  232.     return TRUE;
  233.  
  234. nomem:
  235.     if (ask_yesno((char_u *)"no undo possible; continue anyway") == 'y')
  236.         return TRUE;
  237.     return FALSE;
  238. }
  239.  
  240.     void
  241. u_undo(count)
  242.     int count;
  243. {
  244.     /*
  245.      * If we get an undo command while executing a macro, we behave like the 
  246.      * original vi. If this happens twice in one macro the result will not
  247.      * be compatible.
  248.      */
  249.     if (curbuf->b_u_synced == FALSE)
  250.     {
  251.         u_sync();
  252.         count = 1;
  253.     }
  254.  
  255.     curbuf->b_startop.lnum = 0;            /* unset '[ mark */
  256.     curbuf->b_endop.lnum = 0;                /* unset '] mark */
  257.     u_newcount = 0;
  258.     u_oldcount = 0;
  259.     while (count--)
  260.     {
  261.         if (curbuf->b_u_curhead == NULL)                        /* first undo */
  262.             curbuf->b_u_curhead = curbuf->b_u_newhead;
  263.         else if (p_ul > 0)                            /* multi level undo */
  264.             curbuf->b_u_curhead = curbuf->b_u_curhead->uh_next;            /* get next undo */
  265.  
  266.         if (curbuf->b_u_numhead == 0 || curbuf->b_u_curhead == NULL)    /* nothing to undo */
  267.         {
  268.             curbuf->b_u_curhead = curbuf->b_u_oldhead;                    /* stick curbuf->b_u_curhead at end */
  269.             beep();
  270.             break;
  271.         }
  272.  
  273.         u_undoredo();
  274.     }
  275.     u_undo_end();
  276. }
  277.  
  278.     void
  279. u_redo(count)
  280.     int count;
  281. {
  282.     u_newcount = 0;
  283.     u_oldcount = 0;
  284.     while (count--)
  285.     {
  286.         if (curbuf->b_u_curhead == NULL || p_ul <= 0)        /* nothing to redo */
  287.         {
  288.             beep();
  289.             break;
  290.         }
  291.  
  292.         u_undoredo();
  293.  
  294.         curbuf->b_u_curhead = curbuf->b_u_curhead->uh_prev;            /* advance for next redo */
  295.     }
  296.     u_undo_end();
  297. }
  298.  
  299. /*
  300.  * u_undoredo: common code for undo and redo
  301.  *
  302.  * The lines in the file are replaced by the lines in the entry list at curbuf->b_u_curhead.
  303.  * The replaced lines in the file are saved in the entry list for the next undo/redo.
  304.  */
  305.     static void
  306. u_undoredo()
  307. {
  308.     char_u        **newarray = NULL;
  309.     linenr_t    oldsize;
  310.     linenr_t    newsize;
  311.     linenr_t    top, bot;
  312.     linenr_t    lnum;
  313.     linenr_t    newlnum = MAXLNUM;
  314.     long        i;
  315.     struct u_entry *uep, *nuep;
  316.     struct u_entry *newlist = NULL;
  317.     int            changed = curbuf->b_changed;
  318.     FPOS        namedm[NMARKS];
  319.  
  320.     if (curbuf->b_u_curhead->uh_changed)
  321.         CHANGED;
  322.     else
  323.         UNCHANGED(curbuf);
  324.     /*
  325.      * save marks before undo/redo
  326.      */
  327.     memmove((char *)namedm, (char *)curbuf->b_namedm, sizeof(FPOS) * NMARKS); 
  328.  
  329.     for (uep = curbuf->b_u_curhead->uh_entry; uep != NULL; uep = nuep)
  330.     {
  331.         top = uep->ue_top;
  332.         bot = uep->ue_bot;
  333.         if (bot == 0)
  334.             bot = curbuf->b_ml.ml_line_count + 1;
  335.         if (top > curbuf->b_ml.ml_line_count || top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
  336.         {
  337.             EMSG("u_undo: line numbers wrong");
  338.             CHANGED;        /* don't want UNCHANGED now */
  339.             return;
  340.         }
  341.  
  342.         if (top < newlnum)
  343.         {
  344.             newlnum = top;
  345.             curwin->w_cursor.lnum = top + 1;
  346.         }
  347.         oldsize = bot - top - 1;    /* number of lines before undo */
  348.  
  349.         newsize = uep->ue_size;        /* number of lines after undo */
  350.  
  351.         /* delete the lines between top and bot and save them in newarray */
  352.         if (oldsize)
  353.         {
  354.             if ((newarray = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * oldsize))) == NULL)
  355.             {
  356.                 /*
  357.                  * We have messed up the entry list, repair is impossible.
  358.                  * we have to free the rest of the list.
  359.                  */
  360.                 while (uep != NULL)
  361.                 {
  362.                     nuep = uep->ue_next;
  363.                     u_freeentry(uep, uep->ue_size);
  364.                     uep = nuep;
  365.                 }
  366.                 break;
  367.             }
  368.             /* delete backwards, it goes faster in most cases */
  369.             for (lnum = bot - 1, i = oldsize; --i >= 0; --lnum)
  370.             {
  371.                 newarray[i] = u_save_line(lnum);
  372.                 ml_delete(lnum);
  373.             }
  374.         }
  375.  
  376.         /* insert the lines in u_array between top and bot */
  377.         if (newsize)
  378.         {
  379.             for (lnum = top, i = 0; i < newsize; ++i, ++lnum)
  380.             {
  381.                 ml_append(lnum, uep->ue_array[i], (colnr_t)0, FALSE);
  382.                 u_free_line(uep->ue_array[i]);
  383.             }
  384.             u_free_line((char_u *)uep->ue_array);
  385.         }
  386.  
  387.         /* adjust marks */
  388.         if (oldsize != newsize)
  389.         {
  390.             mark_adjust(top, top + oldsize - 1, MAXLNUM);
  391.             mark_adjust(top + oldsize, MAXLNUM, (long)newsize - (long)oldsize);
  392.         }
  393.  
  394.         u_newcount += newsize;
  395.         u_oldcount += oldsize;
  396.         uep->ue_size = oldsize;
  397.         uep->ue_array = newarray;
  398.         uep->ue_bot = top + newsize + 1;
  399.  
  400.         /*
  401.          * insert this entry in front of the new entry list
  402.          */
  403.         nuep = uep->ue_next;
  404.         uep->ue_next = newlist;
  405.         newlist = uep;
  406.     }
  407.  
  408.     curbuf->b_u_curhead->uh_entry = newlist;
  409.     curbuf->b_u_curhead->uh_changed = changed;
  410.  
  411.     /*
  412.      * restore marks from before undo/redo
  413.      */
  414.     for (i = 0; i < NMARKS; ++i)
  415.         if (curbuf->b_u_curhead->uh_namedm[i].lnum)
  416.         {
  417.             curbuf->b_namedm[i] = curbuf->b_u_curhead->uh_namedm[i];
  418.             curbuf->b_u_curhead->uh_namedm[i] = namedm[i];
  419.         }
  420.  
  421.     if (curbuf->b_u_curhead->uh_cursor.lnum == curwin->w_cursor.lnum)
  422.         curwin->w_cursor.col = curbuf->b_u_curhead->uh_cursor.col;
  423.     else
  424.         curwin->w_cursor.col = 0;
  425. }
  426.  
  427. /*
  428.  * If we deleted or added lines, report the number of less/more lines.
  429.  * Otherwise, report the number of changes (this may be incorrect
  430.  * in some cases, but it's better than nothing).
  431.  */
  432.     static void
  433. u_undo_end()
  434. {
  435.     if ((u_oldcount -= u_newcount) != 0)
  436.         msgmore(-u_oldcount);
  437.     else if (u_newcount > p_report)
  438.         smsg((char_u *)"%ld change%s", u_newcount, plural(u_newcount));
  439.  
  440.     updateScreen(CURSUPD);
  441. }
  442.  
  443. /*
  444.  * u_sync: stop adding to the current entry list
  445.  */
  446.     void
  447. u_sync()
  448. {
  449.     if (curbuf->b_u_synced)
  450.         return;                /* already synced */
  451.     u_getbot();                /* compute ue_bot of previous u_save */
  452.     curbuf->b_u_curhead = NULL;
  453. }
  454.  
  455. /*
  456.  * Called after writing the file and setting b_changed to FALSE.
  457.  * Now an undo means that the buffer is modified.
  458.  */
  459.     void
  460. u_unchanged(buf)
  461.     BUF        *buf;
  462. {
  463.     register struct u_header *uh;
  464.  
  465.     for (uh = buf->b_u_newhead; uh; uh = uh->uh_next)
  466.         uh->uh_changed = 1;
  467.     buf->b_did_warn = FALSE;
  468. }
  469.  
  470. /*
  471.  * u_getbot(): compute the line number of the previous u_save
  472.  *                 It is called only when b_u_synced is FALSE.
  473.  */
  474.     static void
  475. u_getbot()
  476. {
  477.     register struct u_entry *uep;
  478.  
  479.     if (curbuf->b_u_newhead == NULL || (uep = curbuf->b_u_newhead->uh_entry) == NULL)
  480.     {
  481.         EMSG("undo list corrupt");
  482.         return;
  483.     }
  484.  
  485.     if (uep->ue_lcount != 0)
  486.     {
  487.         /*
  488.          * the new ue_bot is computed from the number of lines that has been
  489.          * inserted (0 - deleted) since calling u_save. This is equal to the old
  490.          * line count subtracted from the current line count.
  491.          */
  492.         uep->ue_bot = uep->ue_top + uep->ue_size + 1 + (curbuf->b_ml.ml_line_count - uep->ue_lcount);
  493.         if (uep->ue_bot < 1 || uep->ue_bot > curbuf->b_ml.ml_line_count)
  494.         {
  495.             EMSG("undo line missing");
  496.             uep->ue_bot = uep->ue_top + 1;    /* assume all lines deleted, will get
  497.                                              * all the old lines back without
  498.                                              * deleting the current ones */
  499.         }
  500.         uep->ue_lcount = 0;
  501.     }
  502.  
  503.     curbuf->b_u_synced = TRUE;
  504. }
  505.  
  506. /*
  507.  * u_freelist: free one entry list and adjust the pointers
  508.  */
  509.     static void
  510. u_freelist(uhp)
  511.     struct u_header *uhp;
  512. {
  513.     register struct u_entry *uep, *nuep;
  514.  
  515.     for (uep = uhp->uh_entry; uep != NULL; uep = nuep)
  516.     {
  517.         nuep = uep->ue_next;
  518.         u_freeentry(uep, uep->ue_size);
  519.     }
  520.  
  521.     if (curbuf->b_u_curhead == uhp)
  522.         curbuf->b_u_curhead = NULL;
  523.  
  524.     if (uhp->uh_next == NULL)
  525.         curbuf->b_u_oldhead = uhp->uh_prev;
  526.     else
  527.         uhp->uh_next->uh_prev = uhp->uh_prev;
  528.  
  529.     if (uhp->uh_prev == NULL)
  530.         curbuf->b_u_newhead = uhp->uh_next;
  531.     else
  532.         uhp->uh_prev->uh_next = uhp->uh_next;
  533.  
  534.     u_free_line((char_u *)uhp);
  535.     --curbuf->b_u_numhead;
  536. }
  537.  
  538. /*
  539.  * free entry 'uep' and 'n' lines in uep->ue_array[]
  540.  */
  541.     static void
  542. u_freeentry(uep, n)
  543.     struct u_entry *uep;
  544.     register long n;
  545. {
  546.     while (n)
  547.         u_free_line(uep->ue_array[--n]);
  548.     u_free_line((char_u *)uep);
  549. }
  550.  
  551. /*
  552.  * invalidate the undo buffer; called when storage has already been released
  553.  */
  554.     void
  555. u_clearall(buf)
  556.     BUF        *buf;
  557. {
  558.     buf->b_u_newhead = buf->b_u_oldhead = buf->b_u_curhead = NULL;
  559.     buf->b_u_synced = TRUE;
  560.     buf->b_u_numhead = 0;
  561.     buf->b_u_line_ptr = NULL;
  562.     buf->b_u_line_lnum = 0;
  563. }
  564.  
  565. /*
  566.  * save the line "lnum" for the "U" command
  567.  */
  568.     void
  569. u_saveline(lnum)
  570.     linenr_t lnum;
  571. {
  572.     if (lnum == curbuf->b_u_line_lnum)        /* line is already saved */
  573.         return;
  574.     if (lnum < 1 || lnum > curbuf->b_ml.ml_line_count)    /* should never happen */
  575.         return;
  576.     u_clearline();
  577.     curbuf->b_u_line_lnum = lnum;
  578.     if (curwin->w_cursor.lnum == lnum)
  579.         curbuf->b_u_line_colnr = curwin->w_cursor.col;
  580.     else
  581.         curbuf->b_u_line_colnr = 0;
  582.     curbuf->b_u_line_ptr = u_save_line(lnum);    /* when out of mem alloc() will give a warning */
  583. }
  584.  
  585. /*
  586.  * clear the line saved for the "U" command
  587.  * (this is used externally for crossing a line while in insert mode)
  588.  */
  589.     void
  590. u_clearline()
  591. {
  592.     if (curbuf->b_u_line_ptr != NULL)
  593.     {
  594.         u_free_line(curbuf->b_u_line_ptr);
  595.         curbuf->b_u_line_ptr = NULL;
  596.         curbuf->b_u_line_lnum = 0;
  597.     }
  598. }
  599.  
  600. /*
  601.  * Implementation of the "U" command.
  602.  * Differentiation from vi: "U" can be undone with the next "U".
  603.  * We also allow the cursor to be in another line.
  604.  */
  605.     void
  606. u_undoline()
  607. {
  608.     colnr_t t;
  609.     char_u    *old;
  610.  
  611.     if (curbuf->b_u_line_ptr == NULL || curbuf->b_u_line_lnum > curbuf->b_ml.ml_line_count)
  612.     {
  613.         beep();
  614.         return;
  615.     }
  616.         /* first save the line for the 'u' command */
  617.     u_savecommon(curbuf->b_u_line_lnum - 1, curbuf->b_u_line_lnum + 1, (linenr_t)0);
  618.     old = u_save_line(curbuf->b_u_line_lnum);
  619.     if (old == NULL)
  620.         return;
  621.     ml_replace(curbuf->b_u_line_lnum, curbuf->b_u_line_ptr, TRUE);
  622.     u_free_line(curbuf->b_u_line_ptr);
  623.     curbuf->b_u_line_ptr = old;
  624.  
  625.     t = curbuf->b_u_line_colnr;
  626.     if (curwin->w_cursor.lnum == curbuf->b_u_line_lnum)
  627.         curbuf->b_u_line_colnr = curwin->w_cursor.col;
  628.     curwin->w_cursor.col = t;
  629.     curwin->w_cursor.lnum = curbuf->b_u_line_lnum;
  630.     cursupdate();
  631.     updateScreen(VALID_TO_CURSCHAR);
  632. }
  633.  
  634. /*
  635.  * storage allocation for the undo lines and blocks of the current file
  636.  */
  637.  
  638. /*
  639.  * Memory is allocated in relatively large blocks. These blocks are linked
  640.  * in the allocated block list, headed by curbuf->b_block_head. They are all freed
  641.  * when abandoning a file, so we don't have to free every single line. The
  642.  * list is kept sorted on memory address.
  643.  * block_alloc() allocates a block.
  644.  * m_blockfree() frees all blocks.
  645.  *
  646.  * The available chunks of memory are kept in free chunk lists. There is
  647.  * one free list for each block of allocated memory. The list is kept sorted
  648.  * on memory address.
  649.  * u_alloc_line() gets a chunk from the free lists.
  650.  * u_free_line() returns a chunk to the free lists.
  651.  * curbuf->b_m_search points to the chunk before the chunk that was
  652.  * freed/allocated the last time.
  653.  * curbuf->b_mb_current points to the b_head where curbuf->b_m_search
  654.  * points into the free list.
  655.  *
  656.  *
  657.  *  b_block_head     /---> block #1     /---> block #2
  658.  *       mb_next ---/       mb_next ---/       mb_next ---> NULL
  659.  *       mb_info            mb_info            mb_info
  660.  *          |                  |                  |
  661.  *          V                  V                  V
  662.  *        NULL          free chunk #1.1      free chunk #2.1
  663.  *                             |                  |
  664.  *                             V                  V
  665.  *                      free chunk #1.2          NULL
  666.  *                             |
  667.  *                             V
  668.  *                            NULL
  669.  *
  670.  * When a single free chunk list would have been used, it could take a lot
  671.  * of time in u_free_line() to find the correct place to insert a chunk in the
  672.  * free list. The single free list would become very long when many lines are
  673.  * changed (e.g. with :%s/^M$//).
  674.  */
  675.  
  676.     /*
  677.      * this blocksize is used when allocating new lines
  678.      */
  679. #define MEMBLOCKSIZE 2044
  680.  
  681. /*
  682.  * The size field contains the size of the chunk, including the size field itself.
  683.  *
  684.  * When the chunk is not in-use it is preceded with the m_info structure.
  685.  * The m_next field links it in one of the free chunk lists.
  686.  *
  687.  * On most unix systems structures have to be longword (32 or 64 bit) aligned.
  688.  * On most other systems they are short (16 bit) aligned.
  689.  */
  690.  
  691. /* the structure definitions are now in structs.h */
  692.  
  693. #ifdef ALIGN_LONG
  694.     /* size of m_size */
  695. # define M_OFFSET (sizeof(long_u))
  696. #else
  697.     /* size of m_size */
  698. # define M_OFFSET (sizeof(short_u))
  699. #endif
  700.  
  701. /*
  702.  * Allocate a block of memory and link it in the allocated block list.
  703.  */
  704.     static char_u *
  705. u_blockalloc(size)
  706.     long_u    size;
  707. {
  708.     struct m_block *p;
  709.     struct m_block *mp, *next;
  710.  
  711.     p = (struct m_block *)lalloc(size + sizeof(struct m_block), TRUE);
  712.     if (p != NULL)
  713.     {
  714.          /* Insert the block into the allocated block list, keeping it
  715.                      sorted on address. */
  716.         for (mp = &curbuf->b_block_head; (next = mp->mb_next) != NULL && next < p; mp = next)
  717.             ;
  718.         p->mb_next = next;                /* link in block list */
  719.         mp->mb_next = p;
  720.         p->mb_info.m_next = NULL;        /* clear free list */
  721.         p->mb_info.m_size = 0;
  722.         curbuf->b_mb_current = p;        /* remember current block */
  723.         curbuf->b_m_search = NULL;
  724.         p++;                            /* return usable memory */
  725.     }
  726.     return (char_u *)p;
  727. }
  728.  
  729. /*
  730.  * free all allocated memory blocks for the buffer 'buf'
  731.  */
  732.     void
  733. u_blockfree(buf)
  734.     BUF        *buf;
  735. {
  736.     struct m_block    *p, *np;
  737.  
  738.     for (p = buf->b_block_head.mb_next; p != NULL; p = np)
  739.     {
  740.         np = p->mb_next;
  741.         free(p);
  742.     }
  743.     buf->b_block_head.mb_next = NULL;
  744.     buf->b_m_search = NULL;
  745.     buf->b_mb_current = NULL;
  746. }
  747.  
  748. /*
  749.  * Free a chunk of memory.
  750.  * Insert the chunk into the correct free list, keeping it sorted on address.
  751.  */
  752.     static void
  753. u_free_line(ptr)
  754.     char_u *ptr;
  755. {
  756.     register info_t        *next;
  757.     register info_t        *prev, *curr;
  758.     register info_t        *mp;
  759.     struct m_block        *nextb;
  760.  
  761.     if (ptr == NULL || ptr == IObuff)
  762.         return;    /* illegal address can happen in out-of-memory situations */
  763.  
  764.     mp = (info_t *)(ptr - M_OFFSET);
  765.  
  766.         /* find block where chunk could be a part off */
  767.         /* if we change curbuf->b_mb_current, curbuf->b_m_search is set to NULL */
  768.     if (curbuf->b_mb_current == NULL || mp < (info_t *)curbuf->b_mb_current)
  769.     {
  770.         curbuf->b_mb_current = curbuf->b_block_head.mb_next;
  771.         curbuf->b_m_search = NULL;
  772.     }
  773.     if ((nextb = curbuf->b_mb_current->mb_next) != NULL && (info_t *)nextb < mp)
  774.     {
  775.         curbuf->b_mb_current = nextb;
  776.         curbuf->b_m_search = NULL;
  777.     }
  778.     while ((nextb = curbuf->b_mb_current->mb_next) != NULL && (info_t *)nextb < mp)
  779.         curbuf->b_mb_current = nextb;
  780.  
  781.     curr = NULL;
  782.     /*
  783.      * If mp is smaller than curbuf->b_m_search->m_next go to the start of
  784.      * the free list
  785.      */
  786.     if (curbuf->b_m_search == NULL || mp < (curbuf->b_m_search->m_next))
  787.         next = &(curbuf->b_mb_current->mb_info);
  788.     else
  789.         next = curbuf->b_m_search;
  790.     /*
  791.      * The following loop is executed very often.
  792.      * Therefore it has been optimized at the cost of readability.
  793.      * Keep it fast!
  794.      */
  795. #ifdef SLOW_BUT_EASY_TO_READ
  796.     do
  797.     {
  798.         prev = curr;
  799.         curr = next;
  800.         next = next->m_next;
  801.     }
  802.     while (mp > next && next != NULL);
  803. #else
  804.     do                                        /* first, middle, last */
  805.     {
  806.         prev = next->m_next;                /* curr, next, prev */
  807.         if (prev == NULL || mp <= prev)
  808.         {
  809.             prev = curr;
  810.             curr = next;
  811.             next = next->m_next;
  812.             break;
  813.         }
  814.         curr = prev->m_next;                /* next, prev, curr */
  815.         if (curr == NULL || mp <= curr)
  816.         {
  817.             prev = next;
  818.             curr = prev->m_next;
  819.             next = curr->m_next;
  820.             break;
  821.         }
  822.         next = curr->m_next;                /* prev, curr, next */
  823.     }
  824.     while (mp > next && next != NULL);
  825. #endif
  826.  
  827. /* if *mp and *next are concatenated, join them into one chunk */
  828.     if ((char_u *)mp + mp->m_size == (char_u *)next)
  829.     {
  830.         mp->m_size += next->m_size;
  831.         mp->m_next = next->m_next;
  832.     }
  833.     else
  834.         mp->m_next = next;
  835.  
  836. /* if *curr and *mp are concatenated, join them */
  837.     if (prev != NULL && (char_u *)curr + curr->m_size == (char_u *)mp)
  838.     {
  839.         curr->m_size += mp->m_size;
  840.         curr->m_next = mp->m_next;
  841.         curbuf->b_m_search = prev;
  842.     }
  843.     else
  844.     {
  845.         curr->m_next = mp;
  846.         curbuf->b_m_search = curr;    /* put curbuf->b_m_search before freed chunk */
  847.     }
  848. }
  849.  
  850. /*
  851.  * Allocate and initialize a new line structure with room for at least
  852.  * 'size' characters plus a terminating NUL.
  853.  */
  854.     static char_u *
  855. u_alloc_line(size)
  856.     register unsigned size;
  857. {
  858.     register info_t *mp, *mprev, *mp2;
  859.     struct m_block    *mbp;
  860.     int                 size_align;
  861.  
  862. /*
  863.  * Add room for size field and trailing NUL byte.
  864.  * Adjust for minimal size (must be able to store info_t
  865.  * plus a trailing NUL, so the chunk can be released again)
  866.  */
  867.     size += M_OFFSET + 1;
  868.     if (size < sizeof(info_t) + 1)
  869.       size = sizeof(info_t) + 1;
  870.  
  871. /*
  872.  * round size up for alignment
  873.  */
  874.     size_align = (size + ALIGN_MASK) & ~ALIGN_MASK;
  875.  
  876. /*
  877.  * If curbuf->b_m_search is NULL (uninitialized free list) start at
  878.  * curbuf->b_block_head
  879.  */
  880.     if (curbuf->b_mb_current == NULL || curbuf->b_m_search == NULL)
  881.     {
  882.         curbuf->b_mb_current = &curbuf->b_block_head;
  883.         curbuf->b_m_search = &(curbuf->b_block_head.mb_info);
  884.     }
  885.  
  886. /* search for space in free list */
  887.     mprev = curbuf->b_m_search;
  888.     mbp = curbuf->b_mb_current;
  889.     mp = curbuf->b_m_search->m_next;
  890.     if (mp == NULL)
  891.     {
  892.         if (mbp->mb_next)
  893.             mbp = mbp->mb_next;
  894.         else
  895.             mbp = &curbuf->b_block_head;
  896.         mp = curbuf->b_m_search = &(mbp->mb_info);
  897.     }
  898.     while (mp->m_size < size)
  899.     {
  900.         if (mp == curbuf->b_m_search)        /* back where we started in free chunk list */
  901.         {
  902.             if (mbp->mb_next)
  903.                 mbp = mbp->mb_next;
  904.             else
  905.                 mbp = &curbuf->b_block_head;
  906.             mp = curbuf->b_m_search = &(mbp->mb_info);
  907.             if (mbp == curbuf->b_mb_current)    /* back where we started in block list */
  908.             {
  909.                 int        n = (size_align > (MEMBLOCKSIZE / 4) ? size_align : MEMBLOCKSIZE);
  910.  
  911.                 mp = (info_t *)u_blockalloc((long_u)n);
  912.                 if (mp == NULL)
  913.                     return (NULL);
  914.                 mp->m_size = n;
  915.                 u_free_line((char_u *)mp + M_OFFSET);
  916.                 mp = curbuf->b_m_search;
  917.                 mbp = curbuf->b_mb_current;
  918.             }
  919.         }
  920.         mprev = mp;
  921.         if ((mp = mp->m_next) == NULL)        /* at end of the list */
  922.             mp = &(mbp->mb_info);            /* wrap around to begin */
  923.     }
  924.  
  925. /* if the chunk we found is large enough, split it up in two */
  926.     if ((long)mp->m_size - size_align >= (long)(sizeof(info_t) + 1))
  927.     {
  928.         mp2 = (info_t *)((char_u *)mp + size_align);
  929.         mp2->m_size = mp->m_size - size_align;
  930.         mp2->m_next = mp->m_next;
  931.         mprev->m_next = mp2;
  932.         mp->m_size = size_align;
  933.     }
  934.     else                    /* remove *mp from the free list */
  935.     {
  936.         mprev->m_next = mp->m_next;
  937.     }
  938.     curbuf->b_m_search = mprev;
  939.     curbuf->b_mb_current = mbp;
  940.  
  941.     mp = (info_t *)((char_u *)mp + M_OFFSET);
  942.     *(char_u *)mp = NUL;                    /* set the first byte to NUL */
  943.  
  944.     return ((char_u *)mp);
  945. }
  946.  
  947. /*
  948.  * u_save_line(): allocate memory with u_alloc_line() and copy line 'lnum' into it.
  949.  */
  950.     static char_u *
  951. u_save_line(lnum)
  952.     linenr_t    lnum;
  953. {
  954.     register char_u *src;
  955.     register char_u *dst;
  956.     register unsigned len;
  957.  
  958.     src = ml_get(lnum);
  959.     len = STRLEN(src);
  960.     if ((dst = u_alloc_line(len)) != NULL)
  961.         memmove((char *)dst, (char *)src, (size_t)(len + 1));
  962.     return (dst);
  963. }
  964.